package DP;

/**
 * 背包问题
 */
public class BackPack {

    /**
     * https://www.lintcode.com/problem/backpack/description
     * 数组n，能否拼出 m
     */
//    public int backPack(int m, int[] A) {
//        // write your code here
//        int n =
//
//
//    }
//
//    /**
//     * https://www.lintcode.com/problem/backpack/description
//     * 数组n，能否拼出 m
//     */
//    public int backPackIII(int m, int[] A) {
//        // write your code here
//        int n =
//
//
//    }

    /**
     * 不限制使用次数，数字可重复， 这里问的是多少种组合，有多少种组合
     * F[i] = (F[i]-A0) + (F[i]-A1)
     */
    public int backPackVI(int[] nums, int target) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] dp = new int[target+1];

        dp[0] = 1;//背包0，不用放也算是1种方式
        for(int i=1; i <= target; i++){
            for(int j=0; j<n; j++){
                if(i>=nums[j]){
                    //这里要特别注意，是 dp[i-num[j]]  因为是要看这个数的，而不是数组下标
                    dp[i] += dp[i-nums[j] ];
                }
            }
        }

        return dp[target];
    }

    /**
     * 不限制使用次数，数字可重复， 这里问的是多少种组合，有多少种组合
     * 这是上面的升级版，数字带价值，取出价值最大的那种，思路跟这个差不多
     */
    public int backPackIII(int[] nums, int[] values, int target) {
        int n = nums.length;
        if(n == 0){
            return 0;
        }
        int[] dp = new int[target+1];

        for(int i=1; i<= target; i++){
            dp[i] = -1;//初始化，假设都是不可到达的
        }

        //开始DP，这里记得要从 数字组合开始，而不是从数字开始。 这个跟paint house有点像
        for(int i=1; i<=n; i++){//这里是从1开始，因为下面的地方会取当前的和，前一个的数字的最大的
            for(int j=0; j <= target; j++){
                //这里条件很重要,dp[j-nums[i-1]] 要减去的是当前的num，也就是用 和当前数字组合的情况。
                if( j>=values[i-1] && dp[j-nums[i-1]] != -1){
                    dp[j] = Math.max(dp[j], dp[j-nums[i]] + values[i-1]);
                }
            }
        }
        int res=0;
        for(int i=0; i<target; i++){
            if(dp[i] != -1){
                res = Math.max(res, dp[i]);
            }
        }

        return dp[target];
    }

    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
